<!DOCTYPE html>
<html lang="en">







<head>
 <script>(function(i,s,o,g,r,a,m){i["DaoVoiceObject"]=r;i[r]=i[r]||function(){(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;a.charset="utf-8";m.parentNode.insertBefore(a,m)})(window,document,"script",('https:' == document.location.protocol ? 'https:' : 'http:') + "//widget.daovoice.io/widget/0eeeae6f.js","daovoice")
 daovoice('init', {
  app_id: "246e9537"
});
daovoice('update');
 </script>
  <meta charset="UTF-8">
  <link rel="apple-touch-icon" sizes="76x76" href="/img/apple-touch-icon.png">
  <link rel="icon" type="image/png" href="/img/favicon.png">
  <meta name="viewport"
        content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no, shrink-to-fit=no">
  <meta http-equiv="x-ua-compatible" content="ie=edge">
  
  <meta name="description" content="">

  <meta name="author" content="xixilili">
  <meta name="keywords" content="">
  
  <title>二叉树遍历 ~ xixilili.blog</title>
  <link rel="stylesheet" href="https://cdn.staticfile.org/font-awesome/5.10.2/css/all.min.css"  >
<link rel="stylesheet" href="https://cdn.staticfile.org/twitter-bootstrap/4.3.1/css/bootstrap.min.css"  >
<link rel="stylesheet" href="https://cdn.staticfile.org/mdbootstrap/4.8.9/css/mdb.min.css"  >
<link rel="stylesheet" href="https://cdn.staticfile.org/github-markdown-css/3.0.1/github-markdown.min.css"  >

<link rel="stylesheet" href="//at.alicdn.com/t/font_1067060_qzomjdt8bmp.css">



  <link rel="stylesheet" href="/lib/prettify/tomorrow-night.min.css"  >

<link rel="stylesheet" href="/css/main.css"  >


  <link rel="stylesheet" href="https://cdn.staticfile.org/fancybox/3.5.7/jquery.fancybox.min.css"  >


<meta name="generator" content="Hexo 4.2.0"></head>



<body>
  <header style="height: 70vh;">
    <nav id="navbar" class="navbar fixed-top  navbar-expand-lg navbar-dark scrolling-navbar">
  <div class="container">
    <a class="navbar-brand"
       href="/">&nbsp;<strong>xixilili.blog</strong>&nbsp;</a>

    <button id="navbar-toggler-btn" class="navbar-toggler" type="button" data-toggle="collapse"
            data-target="#navbarSupportedContent"
            aria-controls="navbarSupportedContent" aria-expanded="false" aria-label="Toggle navigation">
      <div class="animated-icon"><span></span><span></span><span></span></div>
    </button>

    <!-- Collapsible content -->
    <div class="collapse navbar-collapse" id="navbarSupportedContent">
      <ul class="navbar-nav ml-auto text-center">
        
          
          
          
          
          <li class="nav-item">
            <a class="nav-link" href="/">Home</a>
          </li>
        
          
          
          
          
          <li class="nav-item">
            <a class="nav-link" href="/archives/">Archives</a>
          </li>
        
          
          
          
          
          <li class="nav-item">
            <a class="nav-link" href="/categories/">Categories</a>
          </li>
        
          
          
          
          
          <li class="nav-item">
            <a class="nav-link" href="/tags/">Tags</a>
          </li>
        
          
          
          
          
          <li class="nav-item">
            <a class="nav-link" href="/about/">About</a>
          </li>
        
        
          <li class="nav-item" id="search-btn">
            <a class="nav-link" data-toggle="modal" data-target="#modalSearch">&nbsp;&nbsp;<i
                class="iconfont icon-search"></i>&nbsp;&nbsp;</a>
          </li>
        
      </ul>
    </div>
  </div>
</nav>

    <div class="view intro-2" id="background"
         style="background: url('https://capsule-1254369940.cos.ap-chengdu.myqcloud.com/xilixiliBg.jpg')no-repeat center center;
           background-size: cover;
           background-attachment: fixed;">
      <div class="full-bg-img">
        <div class="mask rgba-black-light flex-center">
          <div class="container text-center white-text fadeInUp">
            <span class="h2" id="subtitle">
              
            </span>

            
              <br>
              
                <p class="mt-3">
                  <i class="fas fa-calendar-alt" aria-hidden="true"></i>&nbsp;
                  Monday, April 13th 2020, 8:14 pm
                </p>
              

              <p>
                
                  
                  &nbsp;<i class="far fa-chart-bar"></i>
                  <span class="post-count">
                    1.7k 字
                  </span>&nbsp;
                

                
                  
                  &nbsp;<i class="far fa-clock"></i>
                  <span class="post-count">
                      8 分钟
                  </span>&nbsp;
                

                
                  <!-- 不蒜子统计文章PV -->
                  
                  &nbsp;<i class="far fa-eye" aria-hidden="true"></i>&nbsp;
                  <span id="busuanzi_container_page_pv">
                    <span id="busuanzi_value_page_pv"></span> 次
                  </span>&nbsp;
                
              </p>
            
          </div>

          
        </div>
      </div>
    </div>
  </header>

  <main>
    
      




<div class="container-fluid">
  <div class="row">
    <div class="d-none d-lg-block col-lg-2"></div>
    <div class="col-lg-8 nopadding-md">
      <div class="py-5 z-depth-3" id="board">
        <div class="post-content mx-auto" id="post">
          <div class="markdown-body">
            <h2 id="删除二叉搜索树中的节点"><a href="#删除二叉搜索树中的节点" class="headerlink" title="删除二叉搜索树中的节点"></a>删除二叉搜索树中的节点</h2><p>1、删除的结点无左右子节点，那么直接将其父节点指向NULL；<br>2、删除的结点只有1个子节点，分左右两种情况，直接将其父节点指向删除节点的子节点；<br>3、删除节点有2个子节点，这是最麻烦的情况了，最好是画个图理解，具体而言：</p>
<pre><code class="cpp">

    TreeNode* deleteNode(TreeNode* root, int key) {
        if(root==NULL) return NULL;
        if(root-&gt;val==key){
            //情况一和情况二
            if(root-&gt;left==NULL) return root-&gt;right;
            if(root-&gt;right==NULL) return root-&gt;left;
            //情况三:此时需要找到最近的一个大于当前结点值的元素
            TreeNode* RminNode=FindMin(root-&gt;right);
            root-&gt;val=RminNode-&gt;val;
            root-&gt;right=deleteNode(root-&gt;right,RminNode-&gt;val);
        }
        else if(key&lt;root-&gt;val){
            root-&gt;left=deleteNode(root-&gt;left,key);
        }
        else if(key&gt;root-&gt;val){
            root-&gt;right=deleteNode(root-&gt;right,key);
        }
        return root;
    }

    TreeNode* FindMin(TreeNode* root){
        if(root-&gt;left) return FindMin(root-&gt;left);
        else return root;
    }
};</code></pre>
<h2 id="二叉搜索树中的众数"><a href="#二叉搜索树中的众数" class="headerlink" title="二叉搜索树中的众数"></a>二叉搜索树中的众数</h2><p>利用中序求出有序的序列，然后基于这个序列来找</p>
<pre><code class="cpp">int Max_time=0,Max_number,n=0;
    vector&lt;int&gt; v;
    map&lt;int,int&gt; m;
    vector&lt;int&gt; findMode(TreeNode* root) {
        InOrder(root);
        map&lt;int,int&gt;::iterator it;
        for(it=m.begin();it!=m.end();it++){
            if(it-&gt;second&gt;Max_time){
                Max_time=it-&gt;second;
                Max_number=it-&gt;first;
            }
        }
        for(it=m.begin();it!=m.end();it++){
            if(it-&gt;second==Max_time){
                v.push_back(it-&gt;first);
            }
        }

        return v;
    }
    void InOrder(TreeNode* root){
        if(root==NULL) return ;
        InOrder(root-&gt;left);
        if(m.find(root-&gt;val)!=m.end()) m[root-&gt;val]++;//已经存在map中了
        else m.insert(pair&lt;int,int&gt;(root-&gt;val,1));
        InOrder(root-&gt;right);
    }</code></pre>
<h2 id="根据二叉树创建字符串"><a href="#根据二叉树创建字符串" class="headerlink" title="根据二叉树创建字符串"></a>根据二叉树创建字符串</h2><p><img src="https://img-blog.csdnimg.cn/20200413160034387.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NDQwODgy,size_16,color_FFFFFF,t_70" srcset="/img/loading.gif" alt="在这里插入图片描述"><br>利用先序遍历，注意下按照递归的思想去加括号，注意只有右子树存在也要加两对括号</p>
<pre><code class="cpp">    string ans=&quot;&quot;;
    string tree2str(TreeNode* t) {
        PreOrder(t);
        return ans;
    }

    void PreOrder(TreeNode* root){//pos代表当前根结点的位置
        if(root==NULL) return;
        ostringstream os;
        os&lt;&lt;root-&gt;val;
        ans+=os.str();
        if(root-&gt;right){//右子树存在，则左右都要有括号
            ans+=&#39;(&#39;;
            PreOrder(root-&gt;left);
            ans+=&#39;)&#39;;
            ans+=&#39;(&#39;;
            PreOrder(root-&gt;right);
            ans+=&#39;)&#39;;
        }
        else if(root-&gt;left){//只有左子树存在,右子树的括号不用写
            ans+=&#39;(&#39;;
            PreOrder(root-&gt;left);
            ans+=&#39;)&#39;;
        }
    }</code></pre>
<h2 id="二叉树的坡度"><a href="#二叉树的坡度" class="headerlink" title="二叉树的坡度"></a>二叉树的坡度</h2><p><img src="https://img-blog.csdnimg.cn/20200413163023186.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NDQwODgy,size_16,color_FFFFFF,t_70" srcset="/img/loading.gif" alt="在这里插入图片描述"><br>就是一个计算和的递归就行，很简单</p>
<pre><code class="cpp">    int ans=0;
    int findTilt(TreeNode* root) {
        SumTree(root);
        return ans;

    }

    int SumTree(TreeNode* root){
        if(root==NULL) return 0;
        int lsum=SumTree(root-&gt;left);
        int rsum=SumTree(root-&gt;right);
        ans+=abs(lsum-rsum);
        return root-&gt;val+lsum+rsum;

    }</code></pre>
<h2 id="最大二叉树"><a href="#最大二叉树" class="headerlink" title="最大二叉树"></a>最大二叉树</h2><p><img src="https://img-blog.csdnimg.cn/20200413163829449.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NDQwODgy,size_16,color_FFFFFF,t_70" srcset="/img/loading.gif" alt="在这里插入图片描述"><br>用双指针(left,right)+递归实现,注意传参的类型！！</p>
<pre><code class="cpp">    TreeNode* constructMaximumBinaryTree(vector&lt;int&gt;&amp; nums) {
        return solve(nums.begin(),nums.end());
    }

    TreeNode* solve(vector&lt;int&gt;::iterator left, vector&lt;int&gt;::iterator right){
        if(left == right) return NULL;
        auto it = max_element(left,right);
        TreeNode* node = new TreeNode(*it);
        node-&gt;left = solve(left,it);
        node-&gt;right = solve(it+1,right);
        return node;
    }</code></pre>
<h2 id="不同的二叉搜索树-II"><a href="#不同的二叉搜索树-II" class="headerlink" title="不同的二叉搜索树 II"></a>不同的二叉搜索树 II</h2><p><img src="https://img-blog.csdnimg.cn/20200413172420264.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NDQwODgy,size_16,color_FFFFFF,t_70" srcset="/img/loading.gif" alt="在这里插入图片描述"><br>这里递归就是先拆分，得到最底层的值后再合并，<br>拆分就是分成左右子树，最终就是start&gt;end 返回{NULL}。<br>合并的时候要用两个for循环来实现不同的排列。。。<br>注:若只是求种数，可以用卡塔兰数计算<br><img src="https://img-blog.csdnimg.cn/2020041317455984.png" srcset="/img/loading.gif" alt="在这里插入图片描述"></p>
<pre><code class="cpp">vector&lt;TreeNode*&gt; generateTrees(int n) {
        vector&lt;TreeNode*&gt; res;
        if(n==0) return res;
        return generateTreesCore(1, n);

    }
    vector&lt;TreeNode*&gt; generateTreesCore(int start, int end){
        vector&lt;TreeNode*&gt; res;
        if(start&gt;end){
            return {NULL};
        }
        else{
            for(int i = start;i&lt;=end;++i){//表示以i为节点构建树
                vector&lt;TreeNode*&gt; left = generateTreesCore(start, i-1);//构建左子树
                vector&lt;TreeNode*&gt; right = generateTreesCore(i+1, end);//构建右子树

                //此时左右子树都有值.要把他们合并在一起。
                for(auto r: right){
                    for(auto l: left){
                        TreeNode* temp = new TreeNode(i);//把每个节点构建出来。
                        temp-&gt;left = l;
                        temp-&gt;right = r;
                        res.push_back(temp);
                    }
                }
            }
        }
        return res;
    }</code></pre>
<h2 id="恢复二叉搜索树"><a href="#恢复二叉搜索树" class="headerlink" title="恢复二叉搜索树"></a>恢复二叉搜索树</h2><p><img src="https://img-blog.csdnimg.cn/20200413175800603.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NDQwODgy,size_16,color_FFFFFF,t_70" srcset="/img/loading.gif" alt="在这里插入图片描述"></p>
<pre><code class="cpp">     vector&lt;int&gt; order;
    void recoverTree(TreeNode* root) {
        InOrder(root);
        //先得到正确的序列
        sort(order.begin(),order.end());
        recover(root,order);
    }

    void InOrder(TreeNode* root){
        if(root==NULL) return ;
        InOrder(root-&gt;left);
        order.push_back(root-&gt;val);
        InOrder(root-&gt;right);
    }

    void recover(TreeNode* root,vector&lt;int&gt;&amp; rec){
        if(root ==NULL){
            return;
        }
        recover(root-&gt;left,rec);
        //
        if(root-&gt;val == rec[0]){
            rec.erase(rec.begin());
        }else{
            //若不同则修改为相同
            root-&gt;val = rec[0];
            rec.erase(rec.begin());
        };

        recover(root-&gt;right,rec);
    }</code></pre>
<h2 id="二叉树的锯齿形层次遍历"><a href="#二叉树的锯齿形层次遍历" class="headerlink" title="二叉树的锯齿形层次遍历"></a>二叉树的锯齿形层次遍历</h2><pre><code class="cpp">//q1记录正序，q2记录反序
    queue&lt;TreeNode*&gt; q1;
    queue&lt;TreeNode*&gt; q2;
    vector&lt;vector&lt;int&gt;&gt; ans;
    vector&lt;vector&lt;int&gt;&gt; zigzagLevelOrder(TreeNode* root) {
        if(root==NULL) return ans;
        q1.push(root);
        q2.push(root);
        TreeNode* pre_last1=root;
        TreeNode* last1=root;
        TreeNode* pre_last2=root;
        TreeNode* last2=root;
        int level=0;
        vector&lt;int&gt; temp;
        while(!q1.empty()&amp;&amp;!q2.empty()){
            TreeNode* p1=q1.front();
            q1.pop();
            TreeNode* p2=q2.front();
            q2.pop();
            if(p1-&gt;left){
                last1=p1-&gt;left;
                q1.push(p1-&gt;left);
            }
            if(p1-&gt;right){
                last1=p1-&gt;right;
                q1.push(p1-&gt;right);
            }
            if(p2-&gt;right){
                last2=p2-&gt;right;
                q2.push(p2-&gt;right);
            }
            if(p2-&gt;left){
                last2=p2-&gt;left;
                q2.push(p2-&gt;left);
            }
            if(level==0) temp.push_back(p1-&gt;val);
            else temp.push_back(p2-&gt;val);
            //两个同时到达当前行的最后一个
            if(p1==pre_last1){
                pre_last1=last1;
                pre_last2=last2;
                if(level==0){
                    ans.push_back(temp);
                    temp.clear();
                    level=1;
                }
                else{
                    ans.push_back(temp);
                    temp.clear();
                    level=1-level;
                }
            }
        }
        return ans;
    }</code></pre>
<h2 id="路径总和-II"><a href="#路径总和-II" class="headerlink" title="路径总和 II"></a>路径总和 II</h2><p><img src="https://img-blog.csdnimg.cn/20200413200247524.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NDQwODgy,size_16,color_FFFFFF,t_70" srcset="/img/loading.gif" alt="在这里插入图片描述"></p>
<pre><code class="cpp">    int target;
    bool flag=false;
    vector&lt;vector&lt;int&gt;&gt; ans;
    vector&lt;vector&lt;int&gt;&gt; pathSum(TreeNode* root, int sum) {
        if(root==NULL) return ans;
        target=sum;
        vector&lt;int&gt; temp;
        temp.push_back(root-&gt;val);
        dfs(root,0,temp);
        return ans;
    }

    void dfs(TreeNode* root,int sum,vector&lt;int&gt;&amp; temp){
        int cur_sum=sum+root-&gt;val;
        //cout&lt;&lt;cur_sum&lt;&lt;endl;
        if(root-&gt;left==NULL&amp;&amp;root-&gt;right==NULL){
            if(sum+root-&gt;val==target){
                ans.push_back(temp);
                flag=true;
                return ;
            }
        }
            if(root-&gt;left){
                temp.push_back(root-&gt;left-&gt;val);
                dfs(root-&gt;left,cur_sum,temp);
                temp.pop_back();
            }
            if(root-&gt;right){
                temp.push_back(root-&gt;right-&gt;val);
                dfs(root-&gt;right,cur_sum,temp);
                temp.pop_back();
            }
    }</code></pre>
<h2 id="二叉树中的最大路径和"><a href="#二叉树中的最大路径和" class="headerlink" title="二叉树中的最大路径和"></a>二叉树中的最大路径和</h2><p><img src="https://img-blog.csdnimg.cn/20200413200600549.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NDQwODgy,size_16,color_FFFFFF,t_70" srcset="/img/loading.gif" alt="在这里插入图片描述"></p>
<pre><code class="cpp">public:
    int maxh;
    int maxPathSum(TreeNode* root) {
        //if(root==NULL) return 0;
        maxh=root-&gt;val;
        max_path(root);
        return maxh;
    }

    int max_path(TreeNode* root){
        if(root==NULL) return 0;
        int cur=root-&gt;val;
        int l=max_path(root-&gt;left)+cur;
        int r=max_path(root-&gt;right)+cur;
        //cout&lt;&lt;&quot;root&quot;&lt;&lt;root-&gt;val&lt;&lt;endl;
        //cout&lt;&lt;&quot;left:&quot;&lt;&lt;l&lt;&lt;&quot; &quot;&lt;&lt;&quot;right&quot;&lt;&lt;r&lt;&lt;endl;
        if(l&gt;maxh) maxh=l;
        if(r&gt;maxh) maxh=r;
        if(l+r-cur&gt;maxh) maxh=l+r-cur;
        //加上这个是因为有的防止每次计算最大路径都必须包括叶结点(对于已经小于0的分支可以直接抛弃)
        if(l&lt;0&amp;&amp;r&lt;0) return 0;
        else return max(l,r);
    }</code></pre>
<h2 id="二叉搜索树的最近公共祖先"><a href="#二叉搜索树的最近公共祖先" class="headerlink" title="二叉搜索树的最近公共祖先"></a>二叉搜索树的最近公共祖先</h2><p><img src="https://img-blog.csdnimg.cn/20200413201038318.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NDQwODgy,size_16,color_FFFFFF,t_70" srcset="/img/loading.gif" alt="在这里插入图片描述"></p>
<pre><code class="cpp">/*
两个节点p,q分为两种情况：

p和q在相同子树中
p和q在不同子树中
从根节点遍历，递归向左右子树查询节点信息
递归终止条件：如果当前节点为空或等于p或q，则返回当前节点

递归遍历左右子树，如果左右子树查到节点都不为空，则表明p和q分别在左右子树中，因此，当前节点即为最近公共祖先；
如果左右子树其中一个不为空，则返回非空节点。
*/
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==NULL||root==p||root==q) return root; 
        TreeNode* left=lowestCommonAncestor(root-&gt;left,p,q);
        TreeNode* right=lowestCommonAncestor(root-&gt;right,p,q);
        if(left&amp;&amp;right) return root;
        if(left==NULL) return right;
        else return left;
    }</code></pre>

            <hr>
          </div>
          <br>
          <div>
            <p>
            
              <span>
                <i class="iconfont icon-inbox"></i>
                
                  <a class="hover-with-bg" href="/categories/%E7%AE%97%E6%B3%95">算法</a>
                  &nbsp;
                
              </span>&nbsp;&nbsp;
            
            
              <span>
                <i class="iconfont icon-tag"></i>
                
                  <a class="hover-with-bg" href="/tags/c++">c++</a>
                
                  <a class="hover-with-bg" href="/tags/%E6%A0%91">树</a>
                
              </span>
            
            </p>
            
              <p class="note note-warning">本博客所有文章除特别声明外，均采用 <a href="https://zh.wikipedia.org/wiki/Wikipedia:CC_BY-SA_3.0%E5%8D%8F%E8%AE%AE%E6%96%87%E6%9C%AC" target="_blank" rel="nofollow noopener noopener">CC BY-SA 3.0协议</a> 。转载请注明出处！</p>
            
          </div>
        </div>
      </div>
    </div>
    <div class="d-none d-lg-block col-lg-2 toc-container">
      
  <div id="toc">
    <p class="h4"><i class="far fa-list-alt"></i>&nbsp;TOC</p>
    <div id="tocbot"></div>
  </div>

    </div>
  </div>
</div>

<!-- custom -->


<!-- Comments -->
<div class="col-lg-7 mx-auto nopadding-md">
  <div class="container comments mx-auto" id="comments">
    
      <br><br>
      
      
  <!--PC和WAP自适应版-->
  <div id="SOHUCS" sid='http://yoursite.com/2020/04/13/%E4%BA%8C%E5%8F%89%E6%A0%91%E9%81%8D%E5%8E%86/'></div>
  <script type="text/javascript">
    (function () {
      var appid = 'cyuGAy6Y7';
      var conf = '';
      var width = window.innerWidth || document.documentElement.clientWidth;
      if (width < 960) {
        var head = document.getElementsByTagName('head')[0] || document.head || document.documentElement;
        var script = document.createElement('script');
        script.type = 'text/javascript';
        script.charset = 'utf-8';
        script.id = 'changyan_mobile_js';
        script.src = 'https://changyan.sohu.com/upload/mobile/wap-js/changyan_mobile.js?client_id=' + appid + '&conf=' + conf;
        head.appendChild(script);
      } else {
        var loadJs = function (d, a) {
          var c = document.getElementsByTagName('head')[0] || document.head || document.documentElement;
          var b = document.createElement('script');
          b.setAttribute('type', 'text/javascript');
          b.setAttribute('charset', 'UTF-8');
          b.setAttribute('src', d);
          if (typeof a === 'function') {
            if (window.attachEvent) {
              b.onreadystatechange = function () {
                var e = b.readyState;
                if (e === 'loaded' || e === 'complete') {
                  b.onreadystatechange = null;
                  a();
                }
              };
            } else {
              b.onload = a;
            }
          }
          c.appendChild(b);
        };
        loadJs('https://changyan.sohu.com/upload/changyan.js', function () {
          window.changyan.api.config({ appid: appid, conf: conf });
        });
      }
    })(); </script>


    
  </div>
</div>

    
  </main>

  
    <a class="z-depth-1" id="scroll-top-button" href="#" role="button">
      <i class="fa fa-chevron-up scroll-top-arrow" aria-hidden="true"></i>
    </a>
  

  
    <div class="modal fade" id="modalSearch" tabindex="-1" role="dialog" aria-labelledby="ModalLabel"
     aria-hidden="true">
  <div class="modal-dialog modal-dialog-scrollable modal-lg" role="document">
    <div class="modal-content">
      <div class="modal-header text-center">
        <h4 class="modal-title w-100 font-weight-bold">Search</h4>
        <button type="button" id="local-search-close" class="close" data-dismiss="modal" aria-label="Close">
          <span aria-hidden="true">&times;</span>
        </button>
      </div>
      <div class="modal-body mx-3">
        <div class="md-form mb-5">
          <input type="text" id="local-search-input" class="form-control validate">
          <label data-error="x" data-success="v"
                 for="local-search-input">keyword</label>
        </div>
        <div class="list-group" id="local-search-result"></div>
      </div>
    </div>
  </div>
</div>
  

  <footer class="mt-5">
  <div class="text-center py-3">
    <a href="https://hexo.io" target="_blank" rel="nofollow noopener"><b>Hexo</b></a>
    <i class="iconfont icon-love"></i>
    <a href="https://github.com/fluid-dev/hexo-theme-fluid" target="_blank" rel="nofollow noopener"> <b>Fluid</b></a>
    <br>

    
  
    <!-- 不蒜子统计PV -->
    
    &nbsp;<span id="busuanzi_container_site_pv">总访问量 
          <span id="busuanzi_value_site_pv"></span> 次</span>&nbsp;
  
  
    <!-- 不蒜子统计UV -->
    
    &nbsp;<span id="busuanzi_container_site_uv">总访客数 
            <span id="busuanzi_value_site_uv"></span> 人</span>&nbsp;
  
  <br>



    


    <!-- cnzz Analytics icon -->
    

  </div>
</footer>

<!-- SCRIPTS -->
<script src="https://cdn.staticfile.org/jquery/3.4.1/jquery.min.js" ></script>
<script src="https://cdn.staticfile.org/popper.js/1.15.0/umd/popper.min.js" ></script>
<script src="https://cdn.staticfile.org/twitter-bootstrap/4.3.1/js/bootstrap.min.js" ></script>
<script src="https://cdn.staticfile.org/mdbootstrap/4.8.9/js/mdb.min.js" ></script>
<script src="/js/main.js" ></script>


  <script src="/js/lazyload.js" ></script>



  
    <script src="https://cdn.staticfile.org/tocbot/4.8.0/tocbot.min.js" ></script>
  
  <script src="/js/post.js" ></script>



  <script src="https://cdn.staticfile.org/smoothscroll/1.4.10/smooth-scroll.min.js" ></script>



  <script async src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js" ></script>


<!-- Plugins -->


  
    <!-- Baidu Analytics -->
    <script>
      var _hmt = _hmt || [];
      (function () {
        var hm = document.createElement("script");
        hm.src = "https://hm.baidu.com/hm.js?6a61255581242c8c58471dfbffd3bd66# 百度统计的Key，参见 https://tongji.baidu.com/sc-web/10000033910/home/site/getjs?siteId=13751376 代码获取中 hm.js? 后边的字符串";
        var s = document.getElementsByTagName("script")[0];
        s.parentNode.insertBefore(hm, s);
      })();
    </script>
  

  

  

  

  <!-- cnzz Analytics -->
  



  <script src="https://cdn.staticfile.org/prettify/r298/prettify.min.js" ></script>
  <script>
    $(document).ready(function () {
      $('pre').addClass('prettyprint  linenums');
      prettyPrint();
    })
  </script>



  <script src="https://cdn.staticfile.org/typed.js/2.0.10/typed.min.js" ></script>
  <script>
    var typed = new Typed('#subtitle', {
      strings: [
        '  ',
        "二叉树遍历&nbsp;",
      ],
      cursorChar: "_",
      typeSpeed: 70,
      loop: false,
    });
    typed.stop();
    $(document).ready(function () {
      $(".typed-cursor").addClass("h2");
      typed.start();
    });
  </script>



  <script src="https://cdn.staticfile.org/anchor-js/4.2.0/anchor.min.js" ></script>
  <script>
    anchors.options = {
      placement: "right",
      visible: "false",
      
    };
    var el = "h1,h2,h3,h4,h5,h6".split(",");
    var res = [];
    for (item of el) {
      res.push(".markdown-body > " + item)
    }
    anchors.add(res.join(", "))
  </script>



  <script src="/js/local-search.js" ></script>
  <script>
    var path = "/local-search.xml";
    var inputArea = document.querySelector("#local-search-input");
    inputArea.onclick = function () {
      getSearchFile(path);
      this.onclick = null
    }
  </script>



  <script src="https://cdn.staticfile.org/fancybox/3.5.7/jquery.fancybox.min.js" ></script>
  <script>
    $("#post img:not(.no-zoom img, img[no-zoom])").each(
      function () {
        var element = document.createElement("a");
        $(element).attr("data-fancybox", "images");
        $(element).attr("href", $(this).attr("src"));
        $(this).wrap(element);
      }
    );
  </script>





  
  
    <script type="text/javascript">
      //定义获取词语下标
      var a_idx = 0;
      jQuery(document).ready(function ($) {
        //点击body时触发事件
        $("body").click(function (e) {
          //需要显示的词语
          var a = new Array("富强", "民主", "文明", "和谐", "自由", "平等", "公正", "法治", "爱国", "敬业", "诚信", "友善");
          //设置词语给span标签
          var $i = $("<span/>").text(a[a_idx]);
          //下标等于原来下标+1  余 词语总数
          a_idx = (a_idx + 1) % a.length;
          //获取鼠标指针的位置，分别相对于文档的左和右边缘。
          //获取x和y的指针坐标
          var x = e.pageX, y = e.pageY;
          //在鼠标的指针的位置给$i定义的span标签添加css样式
          $i.css({
            "z-index": 999,
            "top": y - 20,
            "left": x,
            "position": "absolute",
            "font-weight": "bold",
            "color": rand_color()
          });
          // 随机颜色
          function rand_color() {
            return "rgb(" + ~~(255 * Math.random()) + "," + ~~(255 * Math.random()) + "," + ~~(255 * Math.random()) + ")"
          }
          //在body添加这个标签
          $("body").append($i);
          //animate() 方法执行 CSS 属性集的自定义动画。
          //该方法通过CSS样式将元素从一个状态改变为另一个状态。CSS属性值是逐渐改变的，这样就可以创建动画效果。
          //详情请看http://www.w3school.com.cn/jquery/effect_animate.asp
          $i.animate({
            //将原来的位置向上移动180
            "top": y - 180,
            "opacity": 0
            //1500动画的速度
          }, 1500, function () {
            //时间到了自动删除
            $i.remove();
          });
        });
      })
      ;
    </script>
  



  <script>(function (i, s, o, g, r, a, m) {
      i['DaoVoiceObject'] = r;
      i[r] = i[r] ||
        function () {
          (i[r].q = i[r].q || []).push(arguments);
        };
      i[r].l = 1 * new Date();
      a = s.createElement(o);
      m = s.getElementsByTagName(o)[0];
      a.async = 1;
      a.src = g;
      a.charset = 'utf-8';
      m.parentNode.insertBefore(a, m);
    })(window, document, 'script', ('https:' === document.location.protocol ? 'https:' : 'http:') + "//widget.daovoice.io/widget/246e9537.js", 'daovoice');
    daovoice('init', {
      app_id: "246e9537",
    });
    daovoice('update');
  </script>




<script src="/live2dw/lib/L2Dwidget.min.js?094cbace49a39548bed64abff5988b05"></script><script>L2Dwidget.init({"pluginModelPath":"assets/","model":{"jsonPath":"/live2dw/assets/wanko.model.json"},"display":{"position":"right","width":150,"height":300},"mobile":{"show":false},"log":false,"pluginJsPath":"lib/","pluginRootPath":"live2dw/","tagMode":false});</script></body>
</html>
